#include <stdio.h>
#include <limits.h>

typedef long int TwoDimArray[ 5 ][ 5 ];

#define Infinity INT_MAX

/* START: fig10_46.txt */
/* Compute optimal ordering of matrix multiplication */
/* C contains number of columns for each of the N matrices */
/* C[ 0 ] is the number of rows in matrix 1 */
/* Minimum number of multiplications is left in M[ 1 ][ N ] */
/* Actual ordering is computed via */
/* another procedure using LastChange */
/* M and LastChange are indexed starting at 1, instead of 0 */
/* Note: Entries below main diagonals of M and LastChange */
/* are meaningless and uninitialized */

void
OptMatrix( const long C[ ], int N,
           TwoDimArray M, TwoDimArray LastChange )
{
    int i, k, Left, Right;
    long ThisM;

    for( Left = 1; Left <= N; Left++ )
        M[ Left ][ Left ] = 0;
    for( k = 1; k < N; k++ )   /* k is Right - Left */
        for( Left = 1; Left <= N - k; Left++ )
        {
            /* For each position */
            Right = Left + k;
            M[ Left ][ Right ] = Infinity;
            for( i = Left; i < Right; i++ )
            {
                ThisM = M[ Left ][ i ] + M[ i + 1 ][ Right ]
                        + C[ Left - 1 ] * C[ i ] * C[ Right ];
                if( ThisM < M[ Left ][ Right ] ) /* Update min */
                {
                    M[ Left ][ Right ] = ThisM;
                    LastChange[ Left ][ Right ] = i;
                }
            }
        }
}
/* END */

main( )
{
    long C[ ] = { 50, 10, 40, 30, 5 };
    long M[ 5 ][ 5 ], LastChange[ 5 ][ 5 ];
    int i, j;

    OptMatrix( C, 4, M, LastChange );
    for( i = 1; i <= 4; i++ )
    {
        for( j = 1; j <= 4; j++ )
            printf( "%14d", M[ i ][ j ] );
        printf( "\n" );
    }
    for( i = 1; i <= 4; i++ )
    {
        for( j = 1; j <= 4; j++ )
            printf( "%14d", LastChange[ i ][ j ] );
        printf( "\n" );
    }
    return 0;
}

